package main.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/9 17:42
 * @description 多看下就理解的更深刻了
 */
public class T15三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        //初始化一个空集合
        List<List<Integer>> result = new ArrayList<>();
        //先判断nums数组里面有没有三个元素
        if (nums.length < 3) {
            return result;
        }
        //对nums数组进行遍历，使之从小到大的排序
        Arrays.sort(nums);
        //开始进行遍历
        for (int i = 0; i < nums.length; i++) {
            //判断：如果第一个元素的内容都大于0了，那么后面的元素都是大于0的，不可能出现三数之和还是为0的情况
            if (nums[i] > 0) {
                break;
            }
            //去重，如果当前元素和上一个元素相同的话，那么得到的结果将会和上一次有相同的部分，如下
            //所以如果当前元素和上一个元素相同的话，就跳过当前元素
            //-2 -2 -1 2 3 4
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //定义两个指针分别指向i的后面一个元素和数组的最后一个元素，从而形成两边往中间靠拢的局势
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
                //判断三数之和能否为0
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //进行去重,看l右面的元素和r左面的元素相同不，相同就跳过该元素
                    //l<r的这个条件记得带上
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else {
                    //判断结果不等于0的情况
                    if (sum > 0) {
                        r--;
                    }
                    if (sum < 0) {
                        l++;
                    }
                }


            }


        }
        return result;
    }

}
